#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long LL;
const LL MOD=100000007;
LL ans[10007];
int main() {
	LL n,k,T;
	cin>>T;
	while (T--) {
		scanf("%lld%lld", &n, &k);
		ans[2]=k*(k-1)%MOD;
		ans[3]=k*(k-1)*(k-2)%MOD;
		for (int i=4; i<=n; ++i) {
			ans[i]=((k-2)*ans[i-1] + (k-1)*ans[i-2])%MOD;
		}
		printf("%lld\n", ans[n]);
	}
	return 0;
}
